#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void swap(int* as, int* aq)
{
	int* tmp = *as;
	*as = *aq;
	*aq = tmp;
}
void charupaixu(int* as, int b)
{
	for (int i = 0; i < b-1; i++)
	{
		int end = i;
		int tmp = as[end + 1];
		while (end >= 0)
		{
			if (as[end] > tmp)
			{
				as[end + 1] = as[end];
				end--;
			}
			else
			{
				break;
			}
		}
		as[end + 1] = tmp;
	}
}
int sanshuquzhong(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[right])
	{
		if (a[mid] < a[right])
		{
			return right;
		}
		else
		{
			if (a[left] > a[mid])
			{
				return mid;
			}
			else
			{
				return left;
			}
		}
	}
	else
	{

		if (a[mid] < a[left])
		{
			return left;
		}
		else
		{
			if (a[right] > a[mid])
			{
				return mid;
			}
			else
			{
				return right;
			}
		}
	}
}
void kuaisu(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if (left + right + 1 < 10)
	{
		charupaixu(a + left, left + right + 1);
	}
	int begin = left;
	int end = right;
	int mid = sanshuquzhong(a, left, right);
	swap(&a[mid], &a[left]);
	int key = left;
	while (begin < end)
	{
		while (begin < end && a[end] >=a[key])
		{
			end--;
		}
		while (begin < end && a[begin] <=a[key])
		{
			begin++;
		}
		swap(&a[end], &a[begin]);
	}
	swap(&a[key], &a[begin]);
	key = begin;
	kuaisu(a,left, key-1);
	kuaisu(a,key + 1, right);
}
int main()
{
	int arr[] = { 524,3,2454,654,7,57,6,765,52,51,34765,8 };
	kuaisu(arr,0, sizeof(arr) / sizeof(arr[0]) - 1);
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}